package com.explorati.LeetCode120.minimumTotal;

import org.omg.PortableInterceptor.INACTIVE;

import java.util.ArrayList;
import java.util.List;

/**
 * @ Author : Weijian_Wang
 * @ Date : Created in 16:43 2020/10/6 0006
 * @ Description ：
 */
public class Solution2 {

    /**
     * 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
     *
     * [
     *      [2],
     *     [3,4],
     *    [6,5,7],
     *   [4,1,8,3]
     * ]
     *
     * @param triangle
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        // 自底向上解法
        // 先从最后一行向上进行相加
        // 转移方程： f[i - 1][[i] = min(f[i][i], f[i][i + 1]) + c[i - 1][i];

        int n = triangle.size() - 1;

        //从最后一行的上一行(triangle.size() - 1 - 1）开始，向逐层向上
        for(int i = n - 1; i >= 0; i --) {
            // 每一行有i个元素
            for(int j = 0; j <= i; j ++) {
                triangle.get(i).set(j,
                        Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)) + triangle.get(i).get(j));
            }
        }

        return triangle.get(0).get(0);
    }

}
